﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MainGame.GameMap;
using Microsoft.Xna.Framework;

namespace GameMap
{
    public class Dijkstra
    {
        private static int VOCUC = -1;
        private int[,] _matrix;
        private int[] _length;
        private int[] _lastV;
        private bool[] _thuocT;
        private int _vertices;
        public int[,] Matrix
        {
            get { return _matrix; }
            set
            {
                _matrix = value;
                _vertices = _matrix.GetLength(0);

                _length = new int[_vertices];
                _lastV = new int[_vertices];
                _thuocT = new bool[_vertices];
            }
        }
        Dictionary<int, Point> mapRCIndexDijstra;
        public Dijkstra(int[,] matrix, Dictionary<int, Point> mapRCIndexDijstra)
        {
            this.Matrix = matrix;
            this.mapRCIndexDijstra = mapRCIndexDijstra;
        }

        public List<Point> FindPath(Point rcStart, Point rcEnd)
        {
            int start = this.GetIndexDijkstra(rcStart);
            int end = this.GetIndexDijkstra(rcEnd);
            if (!(mapRCIndexDijstra.ContainsKey(start) && mapRCIndexDijstra.ContainsKey(end)))
                return null;

            List<Point> path = new List<Point>();
            TimDuong(start, end);
            int i = end;
            do
            {
                path.Add(mapRCIndexDijstra[i]);
                i = _lastV[i];
            } while (i != -1);
            path.Reverse();
            if (path.First().Equals(mapRCIndexDijstra[start]) && path.Last().Equals(mapRCIndexDijstra[end]))
                return path;
            return null;
        }

        private bool TimDuong(int start, int end)
        {
            for (int i = 0; i < _vertices; i++)
            {
                _thuocT[i] = true;
                _length[i] = VOCUC;
                _lastV[i] = -1;
            }
            int v = start;
            int t = start;
            _thuocT[start] = false;
            _length[start] = 0;
            _lastV[start] = -1;
            while (_thuocT[end])
            {
                for (int k = 0; k < _vertices; k++)
                {
                    if (_thuocT[k] == true && _matrix[v, k] != 0 &&
                        (_length[k] == VOCUC || _length[k] > _length[v] + _matrix[v, k]))
                    {
                        _length[k] = _length[v] + _matrix[v, k];
                        _lastV[k] = v;
                    }
                }
                v = -1;
                for (int i = 0; i < _vertices; i++)
                {
                    if (_thuocT[i] == true && _length[i] != VOCUC)
                        if (v == -1 || _length[v] > _length[i])
                        {
                            v = i;
                        }
                }
                if (v != -1)
                    _thuocT[v] = false;
                else return false;
            }
            return true;
        }


        /*Them de phu hop voi map*/
        public int GetIndexDijkstra(Point rc)
        {
            int nRowFull = Math.Max(rc.X - rowStart, 0);
            return nRowFull * (columnEnd - columnStart + 1) + rc.Y - columnStart;
        }

        public int rowStart { get; set; }

        public int columnStart { get; set; }

        public int columnEnd { get; set; }
    }
}